\input{euler.tex}

\begin{document}

\problem[223]{Almost Right-Angled Triangles I}

Let us call an integer sided triangle with sides $a \le b \le c$ \emph{barely acute} if the sides satisfy 
\begin{equation}
a^2 + b^2 = c^2 + 1 . \label{eq:223.1}
\end{equation}

How many barely acute triangles are there with perimeter $\le 25,000,000$?

\solution

Consider the Diophantine equation
\begin{equation}
x^2+y^2=u^2+v^2 , \label{eq:223.11}
\end{equation}
where $x, y, u, v$ are integers. The objective is to find the number of distinct solutions to this equation subject to $x, y, u > 0$, $v=1$ and $x+y+u \le L$. We start by presenting a general parameterization that generates all solutions to equation \eqref{eq:223.11}, from which further analysis can be carried out on equation \eqref{eq:223.1}.

For any integers $m, n, p, q$, note that
\begin{align}
(m^2+n^2)(p^2+q^2) &= (mp+nq)^2 + (mq-np)^2 \notag \\
&= (mp-nq)^2 + (mq+np)^2 . \notag
\end{align}
This presents a parameterized solution for equation \eqref{eq:223.11} if we substitute
\begin{align}
x &= mp+nq , \label{eq:223.p1} \\
y &= mq-np , \label{eq:223.p2} \\
u &= mp-nq , \label{eq:223.p3} \\
v &= mq+np . \label{eq:223.p4}
\end{align}

%and require that $mq-np > 0, mp-nq > 0$, for which a necessary (but not sufficient) condition is $m > n, p>0, q>0$. In addition, a necessary condition for $(x, y, u, v)$ to be primitive is that $(m, n)$ be coprime and $(p, q)$ be coprime.

Conversely, we show below that any solution to equation \eqref{eq:223.11}, possibly after exchanging $u$ and $v$, can be parameterized as in \eqref{eq:223.p1} -- \eqref{eq:223.p4}. First, examine equation \eqref{eq:223.11} and conclude that $x, y, u, v$ must be all odd or all even, or exactly one of $x, y$ is odd and one of $u, v$ is odd. Otherwise equation \eqref{eq:223.11} would contain one or three odd elements (obviously impossible) or two odd elements on one side and two even elements on the other side (also impossible because the odd side would be congruent to 2 mod 4 while the even side would be congruent to 0 mod 4). Hence, without loss of generality, we assume $x \equiv u$ (mod 2) and $y \equiv v$ (mod 2).

If a parameterization as in \eqref{eq:223.p1} -- \eqref{eq:223.p4} does exist, we can solve for $m, n, p, q$ to yield
\begin{equation}
p = \frac{x+u}{2m}, \, 
q = \frac{y+v}{2m}, \,
n = \frac{x-u}{2q} . \label{eq:223.rp}
\end{equation}
To make $p$ and $q$ integral, we could set $m = \frac12 \gcd(x+u, y+v)$. To confirm whether $n$ is integral with this choice of $m$, factorize equation \eqref{eq:223.11} as
\begin{equation}
(x+u)(x-u) = (v+y)(v-y) , \notag
\end{equation}
and divide both sides by $4m$, which yields
\[
p \left( \frac{x-u}{2} \right) = q \left( \frac{v-y}{2}\right) .
\]
Since $q$ divides $p(x-u)/2$ but $p$ and $q$ are coprime, $q$ must divide $(x-u)/2$. Thus $n$ is indeed integral. 

Now we investigate whether the choice of parameters in \eqref{eq:223.rp} is unique, ignoring signs and trivial cases. [To be completed]

%In addition, a necessary condition for $(x, y, u, v)$ to be primitive is that $(m, n)$ be coprime and $(p, q)$ be coprime.

% Finally, if $(x, y, u, v)$ is primitive, then $(m, n, p, q)$ must be pairwise coprime. Otherwise, suppose there exists a prime integer $d > 1$ that divides two of $(m, n, p, q)$. If $d$ divides $(m, n)$ or $d$ divides $(p, q)$, then clearly $d$ divides $(x, y, u, v)$. If $d$ divides $(m, p)$, then $d$ divides $(y,v)$. Examine the equation 
% \[
% (x+u)(x-u) = (v+y)(v-y),
% \]
% it is clear that $d$ must divide $(x+u)(x-u)$, therefore $d$ divides either $x+u$ or $x-u$.

The parameterization in \eqref{eq:223.p1} -- \eqref{eq:223.p4} can be used to generate \emph{all} solutions to equation \eqref{eq:223.11}. In what follows we are only interested in \emph{positive} solutions, i.e. we require $x, y, u, v$ to be positive. This means $m, n, p, q \ge 0$, $mq-np > 0$ and $mp-nq > 0$, for which a necessary (but not sufficient) condition is $m > n \ge 0, p>0, q>0$. 

We now proceed to restrict the choice of parameters in order to eliminate trivial cases and duplicates. First, we require $p \ge q$, because if $p < q$ we can substitute $(m', n', p', q') = (m, n, q, p)$ to yield $(x', y', u', v') = (v, u, y, x)$. In addition, note that if $p = q$, then
\[
x=v=(m+n)p, y=u=(m-n)p,
\]
which is trivial. Note also that if $n = 0$, then $x=u=mp$, $y=v=mq$ is also trivial. Hence non-trivial solutions are generated by $m > n > 0, p > q > 0$. 

With this restriction, we find the useful relation for non-trivial solutions:
\[
x > \{ u, v \} > y .
\]
This means $x$ is the largest element, $y$ is the smallest element, and $u$ and $v$ are in the middle. 
The order of $u$ and $v$, however, is not constrained. A consequence of this is that if $u \ne v$ and $x, y, u, v$ are all odd or all even, then the quadruples $(x, y, u, v)$ and $(x, y, v, u)$ correspond to different sets of $(m, n, p, q)$, and thus will be generated twice. Therefore care must be taken to remove duplicates.

Now return to the original equation \eqref{eq:223.1}. The trivial solutions are $a=1, b=c$, and there are $\lfloor (L-1)/2 \rfloor$ such solutions for $a+b+c \le L$. Non-trivial solutions can be parameterized by
\begin{align}
c &= mp+nq , \label{eq:223.q1} \\
1 &= mq-np , \label{eq:223.q2} \\
a &= mp-nq , \label{eq:223.q3} \\
b &= mq+np . \label{eq:223.q4} 
\end{align}
where
\begin{equation}
m > n > 0, p > q > 0 . \label{eq:223.b2}
\end{equation}
In addition, from equation \eqref{eq:223.q2} we require $\gcd(m, n) = 1$, $\gcd(p, q) = 1$ and $\gcd(m, p) = 1$, and $\gcd(n, q) = 1$. 

Hence, to count the number of solutions $(a,b,c)$ that satisfy \eqref{eq:223.1}, we can instead count the number of quadruples $(m, n, p, q)$ that satisfy \eqref{eq:223.q1} -- \eqref{eq:223.q4} with boundary condition
\begin{equation}
a+b+c = 2p(m+n)+1 \le L . \label{eq:223.b1}
\end{equation}
To do this, we note that equation \eqref{eq:223.q2} is Bézout's identity, for which the solutions can be generated efficiently. [To be completed]
% coefficients enumerate all coprime pairs $(m, p)$ and solve the equation by extended Euclidean algorithm to find $(n, q)$.

Finally, note that if $a, b, c$ are all odd, then $(a,b,c,1)$ and $(b,a,c,1)$ are generated by different parameterizations of $(m, n, p, q)$ and will thus cause double counting. We need to remove the duplicate counts from the answer.

\complexity

From equation \eqref{eq:223.b1} we have $pm \le L/2$. And from equation \eqref{eq:223.b2} we have $m \ge 2, p \ge 2$. The number of solutions to Bézout's identity \eqref{eq:223.q2} is bounded by the number of coprime pairs $(m, p)$, which is in turn bounded by number of pairs $(i,j)$ where $ij \le N = L/2$ and $i,j \ge 2$, which is in turn bounded by 
\[
\sum_{i=2}^N \frac{N}{i} < N \int_1^N \frac{1}{x} \, dx = N \ln N .
\]

Time complexity: $\BigO(L \ln L)$.

Space complexity: $\BigO(\ln L)$.

\answer

61614848

\end{document} 


% We start by rearranging equation \eqref{eq:223.1} as
% \begin{equation}
% (a-1)(a+1) = (c-b)(c+b) . \label{eq:223.2}
% \end{equation}
% To find the number of distinct solutions such that $a + b + c \le L = 25,000,000$, iterate all possible values of $a$ and count the number of solutions $(b,c)$.

% If $a = 1$, equation \eqref{eq:223.2} becomes $b = c$. In this case, $1 + 2b \le L$, so $b \le \lfloor (L-1)/2 \rfloor$. Therefore there are $\lfloor (L-1)/2 \rfloor$ solutions.

% If $a \ge 2$, we can factorize the left-hand side of equation \eqref{eq:223.2} as
% \[
% (a-1)(a+1) = xy
% \]
% where $(x,y)$ is a pair of divisors of $(a-1)(a+1)$. Obviously $(c-b)$ and $(c+b)$ must correspond to one of such pairs of $(x,y)$. Without loss of generality, suppose $x < y$. Solving the equation
% \[
% c-b = x, c+b = y ,
% \]
% we get 
% \begin{equation}
% b = \frac{y-x}{2}, c = \frac{y+x}{2} . \label{eq:223.3}
% \end{equation}
% This is a pair of admissible solution if and only if $x \equiv y (\text{mod } 2)$.

% Hence, we could iterate all $2 \le a \le \lfloor L/3 \rfloor$, factorize $(a-1)(a+1)$, iterate all its divisors $(x,y)$ and solve for $(b,c)$, and count the number of solutions such that $a \le b \le c$. Then adding the number of solutions when $a=1$ gives the answer. 

% However, this approach is very slow for the scale of the problem. (It runs in 47 seconds on a modern PC.) Some improvement is required.
